Sort the array of integers in non-decreasing order.
Input. The
first line contains an integer n (1
≤ n ≤ 1000). The second
line contains n integers, each not
exceeding 2 * 109
in absolute value.
Output. Print all n integers
in non-decreasing order.
|
Sample input |
Sample
output |
|
5 9 2 7 1 2 |
1 2 2 7 9 |
sort
To sort the integers in
non-decreasing order, we can simply use any sorting algorithm or call the sort
function from the Standard Template Library (STL).
Read the input data into an
integer array. Sort the array. Print the contents of the array.
Algorithm realization
Store the input sequence
of integers in the vector v.
vector<int> v;
Read the input data.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
Sort the vector v using the sort function.
sort(v.begin(),v.end());
Print the elements of the vector v in non-decreasing order.
for(i = 0; i < n; i++)
printf("%d ",v[i]);
printf("\n");
Algorithm realization – STL sort, array
Store the input sequence of
integers in the array m.
#define MAX 1010
int m[MAX];
Read the input data.
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&m[i]);
Sort the array m using the sort function.
sort(m,m+n);
Print the elements of the array m in non-decreasing order.
for(i = 0; i < n; i++)
printf("%d ",m[i]);
printf("\n");
STL sort – comparator
#include <cstdio>
#include <algorithm>
#define MAX 1010
using namespace
std;
int m[MAX];
int i, n;
int f(int
a, int b)
{
return a <
b;
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i
< n; i++)
scanf("%d",&m[i]);
sort(m,m+n,f);
for(i = 0; i
< n; i++)
printf("%d
",m[i]);
printf("\n");
return 0;
}
Swap Sort
Swap sort is a simple sorting algorithm that repeatedly
iterates through the array, swapping adjacent elements if they are in the wrong
order.
·
Start
by iterating through the array from the beginning to the end.
·
Compare
each pair of adjacent elements.
·
If the
elements are in the wrong order (e.g., the element at index i is greater
than the element at index i + 1 for ascending order), swap
them.
·
Continue
this process until no more swaps are needed.
·
Repeat
this process until the entire array is sorted.
#include <stdio.h>
#define MAX 1000
int m[MAX];
int i, n;
void sort(void)
{
int i, j,
temp;
for(i = 0; i
< n; i++)
for(j = i +
1; j < n; j++)
if (m[i] > m[j]) temp = m[i], m[i] = m[j], m[j] =
temp;
}
int main(void)
{
scanf("%d",&n);
for(i = 0; i
< n; i++)
scanf("%d",&m[i]);
sort();
for(i = 0; i
< n; i++)
printf("
%d",m[i]);
printf("\n");
return 0;
}
Heap Sort
#include <stdio.h>
#define MAX 1001
int a[MAX];
int n;
int left(int i)
{
return 2 * i;
}
int right(int i)
{
return 2 * i + 1;
}
void swap(int
&i, int &j)
{
int temp
= i; i = j; j =
temp;
}
// max - heap
void heapify(int a[], int i, int n) // n
= size of a heap
{
int
largest = 0;
int l =
left(i);
int r =
right(i);
if (l
<= n && a[l] > a[i]) largest
= l;
else
largest = i;
if (r
<= n && a[r] > a[largest])
largest = r;
if
(largest != i)
{
swap(a[i], a[largest]);
heapify(a,
largest, n);
}
}
void BuildHeap(int a[], int n)
{
for (int i = n / 2;
i > 0; i--)
heapify(a, i, n);
}
void HeapSort(int a[], int n)
{
BuildHeap(a, n);
for (int i = n; i
>= 2; i--)
{
swap(a[1], a[i]);
heapify(a, 1,
i - 1);
}
}
int main(void)
{
scanf("%d",
&n);
for (int i =
1; i <= n; i++)
scanf("%d",
&a[i]);
HeapSort(a,
n);
for (int i =
1; i <= n; i++)
printf("%d
", a[i]);
printf("\n");
return 0;
}
Heap Sort – STL
To work with heap, include
#include <algorithm>
Read the input data.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
Transform the array of numbers into the heap.
make_heap(v.begin(),v.end());
Delete the maximum element
from the heap. Function pop_heap swaps the first and last
elements, decrease the size of the heap by 1 and restores the heap property.
for(i = v.size(); i > 0; i--)
pop_heap(v.begin(),v.begin()
+ i);
Print the sorted array.
for(i = 0; i < v.size(); i++)
printf(" %d",v[i]);
printf("\n");
Quick Sort
We store integers in the
array m.
int m[1010];
Swap two elements.
void swap(int &i, int &j)
{
int temp = i;
i = j; j = temp;
}
Choose as a pivot the leftmost element m[L]. Partition the
array.
int Partition(int L, int R)
{
int x = m[L],
i = L - 1, j = R + 1;
while(1)
{
do j--; while (m[j] > x);
do i++; while (m[i] < x);
if (i <
j) swap(m[i],m[j]); else return j;
}
}
Quick sort of subarray m[L..R].
void QuickSort(int L, int R)
{
int q;
if (L < R)
{
q = Partition(L, R);
QuickSort(L,q); QuickSort(q+1,R);
}
}
The main part of the program.
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&m[i]);
QuickSort(0,n-1);
printf("%d",m[0]);
for(i = 1; i < n; i++) printf("
%d",m[i]);
printf("\n");
Java realization
import java.util.*;
public class
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m[] = new int[n];
for(int i = 0; i < n; i++) m[i] =
con.nextInt();
Arrays.sort(m);
for(int i = 0; i < n; i++)
System.out.print(m[i] + "
");
System.out.println();
con.close();
}
}
Java comparator
import java.util.*;
class f implements
Comparator<Integer>
{
// a <
b means a - b < 0
public int
compare(Integer a, Integer b)
{
return a - b;
}
}
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
Integer m[] = new
Integer[n];
for(int i = 0;
i < n; i++) m[i] = con.nextInt();
Arrays.sort(m, new
f());
for(int i = 0;
i < n; i++)
System.out.print(m[i] + "
");
System.out.println();
con.close();
}
}
Java – heap sort
import java.util.*;
public class Main
{
static int
left(int i)
{
return 2 * i;
}
static int
right(int i)
{
return 2 * i + 1;
}
static void
swap(int a[], int i, int j)
{
int temp = a[i]; a[i] = a[j]; a[j] = temp;
}
//max
- heap
static void
heapify(int a[], int i, int n) //
n = size of a heap
{
int largest = 0;
int l = left(i);
int r = right(i);
if (l
<= n && a[l]
> a[i]) largest = l;
else largest = i;
if (r
<= n && a[r]
> a[largest]) largest = r;
if (largest != i)
{
swap(a, i, largest);
heapify(a, largest, n);
}
}
static void
BuildHeap(int a[], int n)
{
for (int i = n / 2;
i > 0; i--)
heapify(a, i, n);
}
static void
HeapSort(int a[], int n)
{
BuildHeap(a, n);
for (int i = n; i
>= 2; i--)
{
swap(a, 1, i);
heapify(a, 1, i -
1);
}
}
public static void
main(String[] args) {
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
int m[] = new int[n+1];
for(int i = 1;
i <= n; i++)
m[i] = con.nextInt();
HeapSort(m, n);
for(int i = 1;
i <= n; i++)
System.out.print(m[i] + "
");
System.out.println();
con.close();
}
}
Java – swap sort
import java.util.*;
public class Main
{
static void
sort(int m[])
{
for(int i = 0;
i < m.length; i++)
for(int j = i + 1;
j < m.length; j++)
if (m[i]
> m[j])
{
int temp = m[i];
m[i] = m[j];
m[j] = temp;
}
}
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
int n = con.nextInt();
int m[] = new int[n];
for(int i = 0;
i < n; i++) m[i] = con.nextInt();
sort(m);
for(int i = 0;
i < n; i++)
System.out.print(m[i] + "
");
con.close();
}
}
Java – quick Sort
import
java.util.*;
public class
{
public static int Partition (int[] A, int L, int R)
{
int x = A[L], i = L - 1, j = R + 1;
while(true)
{
do j--; while (A[j] > x);
do i++; while (A[i] < x);
if (i < j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
else return j;
}
}
public static void Qsort(int[] A, int L, int R)
{
if (L < R)
{
int q = Partition(A, L,R);
Qsort(A, L,q);
Qsort(A, q+1,R);
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m[] = new int[n];
for(int i = 0; i < n; i++) m[i] =
con.nextInt();
Qsort(m,0,n-1);
for(int i = 0; i < n - 1; i++)
System.out.print(m[i] + "
");
System.out.println(m[n-1]);
}
}
Java – dynamic array
import
java.util.*;
public class
{
public static class DynamicArray
{
private int[] storage;
private int size;
public DynamicArray()
{
storage = new int[100];
size = 0;
}
public DynamicArray(int capacity)
{
storage = new int[capacity];
size = 0;
}
public int length()
{
return size;
}
public void Print()
{
if (size == 0) return;
for(int i = 0; i < size - 1; i++)
System.out.print(storage[i]+ " ");
System.out.println(storage[size-1]);
}
public void ensureCapacity(int minCapacity)
{
int capacity = storage.length;
if (minCapacity > capacity)
{
int newCapacity = (capacity * 3) / 2 + 1;
if (newCapacity < minCapacity) newCapacity = minCapacity;
int temp[] = new int[newCapacity];
System.arraycopy(storage, 0, temp, 0, capacity);
storage = temp;
//storage = Arrays.copyOf(storage, newCapacity);
}
}
private void pack()
{
int capacity = storage.length;
if (size <= capacity / 2)
{
int newCapacity = (size * 3) / 2 + 1;
int temp[] = new int[newCapacity];
System.arraycopy(storage, 0, temp, 0, capacity);
storage = temp;
//storage = Arrays.copyOf(storage, newCapacity);
}
}
public void trim()
{
int newCapacity = size;
int temp[] = new int[newCapacity];
System.arraycopy(storage, 0, temp, 0, storage.length);
storage = temp;
//storage = Arrays.copyOf(storage, newCapacity);
}
private void rangeCheck(int index)
{
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException
("Index: " + index + ", Size: " + size);
}
public void set(int index, int value)
{
rangeCheck(index);
storage[index] = value;
}
public int get(int index)
{
rangeCheck(index);
return storage[index];
}
public void removeAt(int index)
{
rangeCheck(index);
int moveCount = size - index - 1;
if (moveCount > 0)
System.arraycopy(storage, index + 1, storage, index,
moveCount);
size--;
pack();
}
public void insertAt(int index, int value)
{
if (index < 0 || index > size)
throw new IndexOutOfBoundsException
("Index: " + index + ", Size: " + size);
ensureCapacity(size + 1);
int moveCount = size - index;
if (moveCount > 0)
System.arraycopy(storage, index, storage, index + 1,
moveCount);
storage[index] = value;
size++;
}
public void push_back(int value)
{
ensureCapacity(size + 1);
storage[size] = value;
size++;
}
public void Sort()
{
Arrays.sort(storage,0,size);
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
DynamicArray m = new DynamicArray(1);
for(int i = 0; i < n; i++)
m.push_back(con.nextInt());
m.Sort(); m.Print();
}
}
Python realization
Read the input data.
n = int(input())
lst = list(map(int,input().split()))
Sort the list lst using the sort function.
lst.sort()
Print the elements of the list lst in non-decreasing order.
print(*lst)
Python realization – sorted
Read the input data.
n = int(input())
lst = map(int, input().split())
Sort the list lst using the sorted function.
lst = sorted(lst)
Print the elements of the list lst in non-decreasing order.
for i in range(n):
print(lst[i], end=" ")
print()
Python realization – heap sort
def heapify(lst, n, i): # n is size of heap
largest = 0
l = 2
* i # left = 2*i
r = 2
* i + 1
# right = 2*i + 1
if l <= n and lst[l] > lst[i]: largest = l
else: largest = i
if r <= n and lst[r] > lst[largest]: largest = r
if largest != i:
lst[i], lst[largest] = lst[largest], lst[i] # swap
heapify(lst, n, largest)
def BuildHeap(lst, n):
for i in range(n // 2, 0, -1):
heapify(lst, n, i)
def heapSort(lst, n):
BuildHeap(lst, n)
for i in range(n, 1, -1):
lst[i], lst[1] = lst[1], lst[i] # swap
heapify(lst, i - 1, 1)
n = int(input())
lst = list(map(int,input().split()))
lst = [0] + lst
heapSort(lst, n)
for i in range(1,n+1):
print(lst[i], end = " ")